﻿# 算法题库

## 添加题目

- 题目难以程度：Easy、Middle、Hard，添加算法题目时，评估下算法的难以程度
- 备注算法的来源
- 题目描述
- 题目链接

## 答案解析

由于算法题答案的更新可能来自不同的老师，格式差异化较大，或者注释不是很详细，学生看起来比较吃力，算法题答案的格式统一如下：

- 答案的提供者

比如：by 更新答案老师姓名，有录屏需要时，该老师需要再给出录屏

- 算法功能

有些题描述比较长，或者是英文描述，学生可能看不懂算法要完成什么，老师仔细阅读题干，给一个简单的算法功能描述(如果非必要，此项可以省略)

- 算法分析

分析下算法的解题思路，实现步骤，必要时配图讲解

- 算法实现

给出算法的实现过程以及必要的注释说明，若该题有多种解法，可以将各种实现比较下，给出每种方法的优缺点以及时间空间复杂度说明。







#第一部分：字符串相关

--------------------------------------------------------------------------
##第1题---已经出过
- 难度：Easy
- 备注：需要C基础，出自《剑指offer》
- 题目描述
> 请实现一个函数，将一个字符串中的空格替换成“ % 20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are % 20Happy。
>
> void replaceSpace(char *str, int length);
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?tpId=13&tqId=11155&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java

public class Solution {
	public String replaceSpace(StringBuffer str) {
		for (int i = 0; i < str.length(); i++) {
			char v = str.charAt(i);
			if (v == 32) {
				//删除该位置的空格
				str.deleteCharAt(i);
				//在该位置上插入%20
				str.insert(i, new char[]{'%', '2', '0'});
				//由于%20比空格本身多出2个字符，这里添加2，继续下一个处理
				i = i + 2;
			}
		}
		return str.toString();
	}
}


##第2题---已经出过
- 难度：Easy
- 备注：需要C++ string库基础，出自《剑指offer》
- 题目描述
		> 将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
>
> int StrToInt(string str);
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java

public class Solution {

	public int StrToInt(String s) {
		if (s == null) {
			return 0;
		}
		int result = 0;
		boolean negative = false;
		int radix = 10;
		int i = 0;
		int len = s.length();
		int limit = -Integer.MAX_VALUE;
		int multmin;
		int digit;
		if (len > 0) {
			char firstChar = s.charAt(0);
			//考虑： +,-数
			if (firstChar < '0') {
				if (firstChar == '-') {
					negative = true;
					limit = Integer.MIN_VALUE;
				}
				else if (firstChar != '+') {
					return 0;
				}
				//不能只有一个 +,-符号
				if (len == 1) {
					return 0;
				}
				i++;
			}
			multmin = limit / radix;
			while (i < len) {
				//一个字符转化为10进制数字
				digit = Character.digit(s.charAt(i++), radix);
				if (digit < 0) {
					return 0;
				}
				if (result < multmin) {
					return 9;
				}
				result *= radix;
				if (result < limit + digit) {
					return 0;
				}
				result -= digit;
			}
		}
		else {
			return 0;
		}
		return negative ? result : -result;
	}
}

##第3题---已经出过
- 难度：Easy
- 备注：需要C++ string库基础，出自《剑指offer》
- 题目描述
				> 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S = ”abcXYZdef”, 要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
				>
				> string LeftRotateString(string str, int n);
			>
			>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java

			public class Solution {
				public String LeftRotateString(String str, int n) {
					if (str == null || "".equals(str)){
						return str;
					}
					return str.substring(n) + str.substring(0, n);
				}
			}

##第4题---已经出过
			- 难度：	Medium
				- 备注：需要C++ vector、string库基础，出自《剑指offer》
				- 题目描述
> 输入一个字符串, 按字典序打印出该字符串中字符的所有排列。例如输入字符串abc, 则打印出由字符a, b, c所能排列出来的所有字符串abc, acb, bac, bca, cab和cba。输入描述：输入一个字符串, 长度不超过9(可能有字符重复), 字符只包括大小写字母。
>
> vector<string> Permutation(string str)；
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)



### 答案-Java

			public class SolutionDay4 {

				public ArrayList<String> Permutation(String str) {
					//如果为空，直接返回
					if (str == null || str.length() == 0) {
						return new ArrayList<>();
					}
					//将字符串转换为字符数组
					char[] chars = str.toCharArray();
					//创建接收结果的集合
					TreeSet<String> result = new TreeSet<>();
					Permutation(chars, 0, result);
					return new ArrayList<>(result);
				}

				private void Permutation(char[] chars, int index, TreeSet<String> result) {
					if (index < 0 || index > chars.length - 1) {
						return;
					}
					if (index == chars.length - 1) {
						result.add(String.valueOf(chars));
					}
					else {
						for (int i = index; i <= chars.length - 1; i++) {
							swap(chars, index, i);//交换元素
							Permutation(chars, index + 1, result);//继续从下一个位置开始排列
							swap(chars, index, i);//元素复位
						}
					}
				}

				/**
				* 交换数组中两个指定位置的元素
				*/
				private void swap(char[] x, int a, int b) {
					char t = x[a];
					x[a] = x[b];
					x[b] = t;
				}
			}


##第5题---已经出过

			- 难度：	Medium
				- 备注：需要C++ string库基础，出自《剑指offer》
				- 题目描述
> 在一个字符串(1 <= 字符串长度 <= 10000，全部由字母组成)中找到第一个只出现一次的字符, 并返回它的位置
>
> int FirstNotRepeatingChar(string str);
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-C/C++

class Solution {
public:
	int FirstNotRepeatingChar(string str) {
		int arr[255];   // 这个数组用来保存每个ascii值的出现次数
		int idx = 0;
		for (int i = 0; i<255; i++)
			arr[i] = 0;

		int len = str.length();

		// 扫描字符串，将字符的出现次数累加到arr数组
		for (int i = 0; i<len; i++) {
			arr[str[i]]++;
		}

		// 扫描字符串，第一次出现次数为1的字母，返回其下标
		for (int i = 0; i<len; i++) {
			if (arr[str[i]] == 1)
				return i;
		}
		return -1;
	}
};


### 答案-Java

public class Solution {
	public int FirstNotRepeatingChar(String str) {
		if (str == null){
			return -1;
		}
		int[] arr = new int[255]; //ASCII范围
		for (int i = 0, len = str.length(); i<len; i++){
			arr[str.charAt(i)]++;   //计算每个ASCII码的数量
		}
		for (int i = 0, len = str.length(); i<len; i++){
			if (arr[str.charAt(i)] == 1){
				return i;           //找到第一个出现1次的返回字符下标
			}
		}
		return -1;
	}
}

##第6题---已经出过
- 难度：	Medium
- 备注：需要C++ string库基础，出自《剑指offer》
- 题目描述
		> 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student.a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
		>
		> string ReverseSentence(string str)；
		>
		>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=11197&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


### 答案-C/C++

class Solution {
public:
	string ReverseSentence(string str) {
		int len = str.length();   // 求出字符串长度
		reverse(str.begin(), str.end()); // 翻转整个字符串
		int from = 0; // 用于保存单词开始位置
		int i = 0;
		int to; // 保存单词结束位置的下一个位置
		while (i < len) {
			if (!isspace(str[i])) { //  如果不是空白符，说明是单词开始
				from = i;            //  from保存单词开始位置
				while (i<len && !isspace(str[i])) { // 找单词结尾
					i++;
				}
				to = i; // to保存单词结尾的下一个位置
				reverse(str.begin() + from, str.begin() + to); // 逆置单词
			}
			i++;
		}
	}
};


### 答案-Java

public class Solution {
	public String ReverseSentence(String str) {
		//判断null和多个空格字符串
		if (str == null || str.trim().equals("")) {
			return str;
		}
		//用空格切分单词
		String[] words = str.split(" ");
		StringBuilder sb = new StringBuilder(str.length());
		for (int i = words.length - 1; i > 0; i--) {
			sb.append(words[i]).append(" ");
		}
		sb.append(words[0]);
		return sb.toString();
	}
}


##第7题---已经出过

- 难度：	Medium
- 备注：需要C++ string库基础，出自《剑指offer》
- 题目描述
		>请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
>
> bool match(char* str, char* pattern)；
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)



### 答案-Java 

public class Solution {

	public boolean match(char[] str, char[] pattern) {
		return matchTwo(str, 0, str.length, pattern, 0, pattern.length);
	}

	private boolean matchTwo(char[] str, int i, int str_len, char[] pattern, int j, int pattern_len) {
		//特殊情况：字符串和模式都为空，那么匹配
		if (i == str_len && j == pattern_len) {
			return true;
		}
		//特殊情况：字符串为空，模式不为空  比如：模式为a*a*a*a*， *之前的字符可以出现0次或者多次
		if (i == str_len && j != pattern_len) {
			while (j != pattern_len) {
				if (pattern[j] != '*' && (j + 1 >= pattern_len || pattern[j + 1] != '*')) {
					return false;
				}
				j++;
			}
			return true;
		}
		//特殊情况：字符串不为空，模式为空，无法匹配，返回false
		if (i != str_len && j == pattern_len) {
			return false;
		}

		//模式匹配：模式下一个字符不是*
		if (j + 1 == pattern_len) {
			//原字符串和模式移动1位
			if (str[i] == pattern[j] || pattern[j] == '.') {
				return matchTwo(str, i + 1, str_len, pattern, j + 1, pattern_len);
			}
			else {
				return false;
			}
		}
		if ((str[i] == pattern[j] || pattern[j] == '.') && pattern[j + 1] != '*') {
			return matchTwo(str, i + 1, str_len, pattern, j + 1, pattern_len);
		}

		//模式匹配：模式下一个字符是*
		if ((str[i] == pattern[j] || pattern[j] == '.') && pattern[j + 1] == '*') {
			//模式匹配1个或者多个字符 ； 模式匹配0个字符
			return matchTwo(str, i + 1, str_len, pattern, j, pattern_len) || matchTwo(str, i, str_len, pattern, j + 2, pattern_len);
		}
		if (pattern[j + 1] == '*') {
			return matchTwo(str, i, str_len, pattern, j + 2, pattern_len);
		}

		return false;
	}
}


##第8题--找不到

- 难度：	Medium
- 备注：需要C++ string库基础，出自《剑指offer》
- 题目描述
>请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100", "5e2", "-123", "3.1416"和"-1E-16"都表示数值。 但是"12e", "1a3.14", "1.2.3", "+-5"和"12e+4.3"都不是。
>
> bool isNumeric(char* string)；
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/6f8c901d091949a5837e24bb82a731f2?tpId=13&tqId=11206&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java

**正则表达式的方式**

public class Solution {
	public boolean isNumeric(char[] str) {
		String string = String.valueOf(str);
		return string.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
	}
}

**分类检查的方式**

public class Solution {

	/**
	* 检查元素是否在数组中存在，存在返回true否则返回false
	*/
	private boolean contains(char[] str, char ch) {
		for (char c : str) {
			if (c == ch) {
				return true;
			}
		}
		return false;
	}

	/**
	* 截取数组中指定返回的元素[start,end)，左开右闭区间
	*/
	private char[] subChars(char[] str, int start, int end) {
		char[] ret = new char[end - start];
		System.arraycopy(str, start, ret, 0, end - start);
		return ret;
	}

	/**
	* 判断字符数组是否是纯数字
	*/
	private boolean isDigit(char[] str) {
		for (char c : str) {
			if (c < '0' || c > '9') {
				return false;
			}
		}
		return true;
	}

	/**
	* 判断字符数组是否以指定字符开头
	*/
	private boolean startWith(char[] str, char ch) {
		return str[0] == ch;
	}

	/**
	* 判断字符数组中第一次出现指定字符的位置
	*/
	private int indexOf(char[] str, char ch) {
		int posE = -1;
		for (int i = 0; i < str.length; i++) {
			if (str[i] == ch) {
				posE = i;
				break;
			}
		}
		return posE;
	}

	/**
	* 判断小数
	*/
	private boolean isDecimal(char[] str) {
		if (startWith(str, '-') || startWith(str, '+')) {
			str = subChars(str, 1, str.length);
		}
		if (contains(str, '.')) {//如果是小数
			int posE = indexOf(str, '.');
			if (posE == 0 || posE == str.length - 1) {
				return true;
			}
			//左右两部分分割，不含小数点符号
			char[] left = subChars(str, 0, posE);
			char[] right = subChars(str, posE + 1, str.length);
			return isDigit(left) && isDigit(right);
		}
		else {//如果不是小数
			return isDigit(str);
		}
	}

	/**
	* 判断科学计数
	*/
	private boolean isScientificNotation(char[] str) {
		int posE = indexOf(str, 'E');
		posE = posE == -1 ? indexOf(str, 'e') : posE;
		//如果E或者e在开始位置与结束位置，说明错误
		if (posE == 0 || posE == str.length - 1) {
			return false;
		}
		//左右两部分分割，不含E或者e符号
		char[] left = subChars(str, 0, posE);
		char[] right = subChars(str, posE + 1, str.length);
		if (startWith(right, '-') || startWith(right, '+')) {
			right = subChars(right, 1, right.length);
		}
		return isDecimal(left) && isDigit(right);
	}

	public boolean isNumeric(char[] str) {
		if (contains(str, 'E') || contains(str, 'e')) {//科学计数法
			return isScientificNotation(str);
		}
		else {
			return isDecimal(str);
		}
	}
}

-------------------------------------------------------------------- -
#数组

-------------------------------------------------------------------- -

##第1题---已经出过
- 难度：	Medium
- 备注：需要C++ vector、string库基础，出自《剑指offer》
- 题目描述
		> 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
>
> bool Find(int target, vector<vector<int> > array);
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


### 答案-Java

public class Solution {

	public boolean Find(int target, int[][] array) {
		for (int x = 0; x < array.length; x++) {
			for (int y = 0; y < array[x].length; y++) {
				int value = array[x][y];
				if (value > target) {
					break;
				}
				if (value == target) {
					return true;
				}
			}
		}
		return false;
	}

}

##第2题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
		> 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{ 1, 2, 3, 2, 2, 2, 5, 4, 2 }。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
>
> ```int MoreThanHalfNum_Solution(vector<int> numbers)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


### 答案-Java


import java.util.Arrays;

public class Solution {

	public int MoreThanHalfNum_Solution(int[] array) {
		if (array.length == 0) {
			return 0;
		}
		Arrays.sort(array);
		int num = array[array.length / 2];
		int count = 0;
		for (int anArray : array) {
			if (num == anArray) {
				count++;
			}
		}
		if (count > (array.length / 2)) {
			return num;
		}
		else {
			return 0;
		}
	}
}

##第3题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
> 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
>
> ```int GetUglyNumber_Solution(int index)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b?tpId=13&tqId=11186&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


### 答案-Java


public class SolutionDay3 {

	int GetUglyNumber_Solution(int index) {
		if (index <= 0) {
			return 0;
		}
		int[] ugly = new int[index];
		ugly[0] = 1;
		int u2 = 0, u3 = 0, u5 = 0;
		int count = 0;
		while (count < index - 1) {
			int u = Math.min(ugly[u2] * 2, Math.min(ugly[u3] * 3, ugly[u5] * 5));
			if (u == ugly[u2] * 2) {
				u2++;
			}
			if (u == ugly[u3] * 3) {
				u3++;
			}
			if (u == ugly[u5] * 5) {
				u5++;
			}
			ugly[++count] = u;
		}
		return ugly[index - 1];
	}
}


##第4题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
		> 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组, 求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P % 1000000007
>

-输入描述:
> 题目保证输入的数组中没有的相同的数字
> 数据范围：
> 1. 对于 % 50的数据, size <= 10 ^ 4
> 2. 对于 % 75的数据, size <= 10 ^ 5
> 3. 对于 % 100的数据, size <= 2 * 10 ^ 5

- 示例1
> 输入:1, 2, 3, 4, 5, 6, 7, 0
> 输出:7
>
> ```int InversePairs(vector<int> data); ```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第5题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
> 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{ 3，32，321 }，则打印出这三个数字能排成的最小数字为321323。
>
> ```string PrintMinNumber(vector<int> numbers)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)



答案 - C++

```c+ +
/*
对vector容器内的数据进行排序，按照 将a和b转为string后
 若 a＋b<b+a  a排在在前 的规则排序,
  如 2 21 因为 212 < 221 所以 排序后为 21 2 
    to_string() 可以将int 转化为string
	*/
class Solution {
public:
	static bool cmp(int a, int b){
		string A = "";
		string B = "";
		A += to_string(a);
		A += to_string(b);
		B += to_string(b);
		B += to_string(a);

		return A<B;
	}
	string PrintMinNumber(vector<int> numbers) {
		string  answer = "";
		sort(numbers.begin(), numbers.end(), cmp);
		for (int i = 0; i<numbers.size(); i++){
			answer += to_string(numbers[i]);
		}
		return answer;
	}
};
```



##第6题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
		> 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{ 3, 4, 5, 1, 2 }为{ 1, 2, 3, 4, 5 }的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
		>
> ```int minNumberInRotateArray(vector<int> rotateArray)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第7题--找不到
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
> 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{ 3, 4, 5, 1, 2 }为{ 1, 2, 3, 4, 5 }的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
>
> ```int minNumberInRotateArray(vector<int> rotateArray)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第8题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
> 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
>
> ```void reOrderArray(vector<int> &array)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?tpId=13&tqId=11166&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第9题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
> 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
> 例如，如果输入如下矩阵：
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
> 13 14 15 16
> 则依次打印出数字
> 1, 2, 3, 4
> 8, 12, 16, 15
> 14, 13, 9, 5
> 6, 7, 11, 10
>
> ```vector<int> printMatrix(vector<vector<int> > matrix)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第10题---和上一个重复
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
> 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
> 例如，如果输入如下矩阵：
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
> 13 14 15 16
> 则依次打印出数字
> 1, 2, 3, 4
> 8, 12, 16, 15
> 14, 13, 9, 5
> 6, 7, 11, 10
>
> ```vector<int> printMatrix(vector<vector<int> > matrix)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第11题----已经出过

- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1, 2, 1]，和最大的连续子数组为[2, 1]，其和为 3

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素, 每个整数都在32位int范围内。以空格分隔。


输出描述 :

所有连续子数组中和最大的值。
示例1
输入

3 - 1 2 1
输出
3

链接：https://www.nowcoder.com/questionTerminal/5a304c109a544aef9b583dce23f5f5db
来源：牛客网


##第12题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
统计一个数字在排序数组中出现的次数。
>
> ```int GetNumberOfK(vector<int> data, int k)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第13题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
>
> ```void FindNumsAppearOnce(vector<int> data, int* num1, int *num2)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&tqId=11193&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第14题---已经出过
- 难度：	Hard（动态规划）
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
小明很喜欢数学, 有一天他在做数学作业时, 要求计算出9~16的和, 他马上就写出了正确答案是100。但是他并不满足于此, 他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久, 他就得到另一组连续正数和为100的序列:18, 19, 20, 21, 22。现在把问题交给你, 你能不能也很快的找出所有和为S的连续正数序列 ? Good Luck!
- 输出描述 :
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
>
> ```vector<vector<int> > FindContinuousSequence(int sum)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)



答案 - C++

```
// 指定区间 [plow, phigh].
// 计算该区间的和(直接使用等差数列求和公式)
// 当总和小于sum，phigh继续+1
// 否则plow+1
class Solution {
public:
	vector<vector<int> > FindContinuousSequence(int sum) {
		vector<vector<int> > allRes;
		// 起始位置的数字和结束位置的数字.
		// [plow, phigh] 区间
		int phigh = 2, plow = 1;

		while (phigh > plow){
			// 使用等差数列求和公式直接计算区间的和
			int cur = (phigh + plow) * (phigh - plow + 1) / 2;
			if (cur < sum)
				phigh++;

			if (cur == sum){
				vector<int> res;
				for (int i = plow; i <= phigh; i++)
					res.push_back(i);
				allRes.push_back(res);
				plow++;
			}

			if (cur > sum)
				plow++;
		}

		return allRes;
	}
};
```



##第15题---找不到
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
- 输出描述:
对应每个测试案例，输出两个数，小的先输出。
>
> ```vector<int> FindNumbersWithSum(vector<int> array, int sum)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第16题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
在一个长度为n的数组里的所有数字都在0到n - 1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{ 2, 3, 1, 0, 2, 5, 3 }，那么对应的输出是第一个重复的数字2。
>
> ```bool duplicate(int numbers[], int length, int* duplication)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

class Solution {
public:
	// Parameters:
	//        numbers:     an array of integers
	//        length:      the length of array numbers
	//        duplication: (Output) the duplicated number in the array number
	// Return value:       true if the input is valid, and there are some duplications in the array number
	//                     otherwise false
	bool duplicate(int numbers[], int length, int* duplication) {
		sort(numbers, numbers + length); // 排序，然后比较相邻的数据是否相等。
		bool flag = false;  // 如果相等，赋值为true
		for (int i = 0; i<length - 1; i++) {
			if (numbers[i] == numbers[i + 1]) {
				*duplication = numbers[i];
				flag = true;
				break;
			}
		}
		return flag;
	}
};

##第17题----6/6出
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
给定一个数组A[0, 1, ..., n - 1], 请构建一个数组B[0, 1, ..., n - 1], 其中B中的元素B[i] = A[0] * A[1] * ...*A[i - 1] * A[i + 1] * ...*A[n - 1]。不能使用除法。
		>
> ```vector<int> multiply(const vector<int>& A)；```
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/94a4d381a68b47b7a8bed86f2975db46?tpId=13&tqId=11204&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
>
> ```cpp
> class Solution {
>
> public:
>
>   vector<int> multiply(const vector<int>& A) {
>       vector<int> ret;
>       int len = A.size();
>       if (len == 0)
>         return ret;
>
>    for (int i = 0; i<len; i++) {
>    		int tmp = 1;
>    		int cnt = 0;  // 记录A数组的下标
> 		for (auto &item : A) {
>             if (cnt == i) { // A数组下标和ret的下标值相等，不做累乘，继续找下一个数。
>             	cnt++;
>    				continue;
>
}
else {
>    				cnt++;
>        			tmp *= item;
>
}
>
}
> 		ret.push_back(tmp);
>
}
>
>    return ret;
>
}
>
};
>
> ```

-------------------------------------------------------------------- -
#链表
-------------------------------------------------------------------- -

##第1题---已经出过
- 难度：	Medium
- 备注：需要C++ vector库基础，出自《剑指offer》
- 题目描述
输入一个链表，输出该链表中倒数第k个结点。
###答案C++

> ```ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)```
>
> ```cpp
> // by 时亮益
> class Solution {
>
> public:
>
>     /*
	  >
	  >     使用前后快慢指针解决。
	  >
	  >     思路：
	  >
	  >       1. pFast指针先向后走n步(或者走n-1步)
	  >
	  >       2. pSlow和pFast两个指针同时向后移动，直到pFast走到链表的结尾（直到pFast走到链表最后一个节点位置），pSlow所在位置刚好为倒数第K个结点
	  >
	  >     */
>
>     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
>
>         // 参数检测：如果是空链表，或者k为0(即倒数第0个)，没有办法找，直接返回
>
>         if (NULL == pListHead || 0 == k)
>
>             return NULL;
>
>     ListNode* pFast = pListHead;
>
>     // pFast先向后走n步
>     while (k--)
>     {
>         // k大于链表中结点的个数，倒数第K个结点不存在，返回NULL
>         if (NULL == pFast)
>             return NULL;
>
>         pFast = pFast->next;
>     }
>
>      // 两个指针同时向后走，直到pFast走到链表的末尾,pFast即为倒数第K个结点
>     ListNode* pSlow = pListHead;
>     while (pFast)
>     {
>         pFast = pFast->next;
>         pSlow = pSlow->next;
>     }
>
>     /* 方法二：
	  >     // pFast先向后走n-1步
	  >     while(--k)
	  >     {
	  >         if(NULL == pFast)
	  >             return NULL;
	  >
	  >         pFast = pFast->next;
	  >     }
	  >
	  >     // 注意循环结束后，pFast有可能为空，比如链表为1--->2--->3--->NULL, k为4
	  >     if(NULL == pFast)
	  >         return NULL;
	  >
	  >      //两个指针同时向后走，直到pFast走到链表的最后一个节点位置,pFast即为倒数第K个结点
	  >     ListNode* pSlow = pListHead;
	  >     while(pFast->next)
	  >     {
	  >         pFast = pFast->next;
	  >         pSlow = pSlow->next;
	  >     }
	  >     */
>
>     return pSlow;
>
}
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


### 答案-Java


//龟兔赛跑，让兔先跑 k 步，然后龟和兔继续跑，兔到终点后的继续跑结点为null表示结束，此时龟的位置就是倒数 k 的结点
public class SolutionDay1 {


	​
	public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}

	public ListNode FindKthToTail(ListNode head, int k) {
		if (head == null || k == 0) {
			return null;
		}
		ListNode fast = head;
		ListNode slow = head;
		for (int i = 0; i < k; i++) {
			if (fast == null) {
				return null;
			}
			fast = fast.next;
		}
		while (fast != null) {
			fast = fast.next;
			slow = slow.next;
		}
		return slow;
	}
}



##第2题---已经出过
- 难度：	Easy
- 备注：需要C++ vector库基础、链表基础，出自《剑指offer》
- 题目描述
输入一个链表，从尾到头打印链表每个节点的值。
###答案C++

		> ```vector<int> printListFromTailToHead(ListNode* head)```
>
> ```cpp
> /*
  > by 时亮益
  > 方法一：
  >   将链表中结点中值全部保存在vector中，然后将vector逆序即可。
  > */
> #include <algorithm>
> class Solution {
> public:
>     vector<int> printListFromTailToHead(ListNode* head) {
>         vector<int> v;
>         ListNode* pCur = head;
>         while (pCur)
>         {
>             // 因为提前不知道链表的长度，此处只能使用push_back()函数一个一个插入
>             v.push_back(pCur->val);
>             pCur = pCur->next;
>         }
>
>         // 将vector中的元素逆序
>         std::reverse(v.begin(), v.end());
>         return v;
>
}
>
};
> /*
  > 说明：
  >   时间复杂度：O(N)，空间复杂度：O(N)
  >   此种方式虽然可以，但是并不是面试官想看到的方式。
  >   缺陷：使用vector中push_back方法，push_back在进行插入时，一旦需要增容，其效率就会大大收影响(开辟新空间--->拷贝元素--->释放就空间)
  > */
> ```
>
>
>
> ```cpp
> // 方法二：使用递归
> /*
  > 1----->2----->3----->4----->5----->NULL
  > 分析：
  >   逆向打印，直观想法从最后一个节点开始打印，然后打印其前一个，直到链表中所有的结点均打印完成。
  >   问题是：链表是单链表，知道后一个结点无法知道其前一个结点，因此不能直接按照此种方式打印。
  >
  >   如果把1后面的所有节点能够逆序完，最后打印结点1，此链表即可逆序打印。
  >   因为1后的所有节点，也是单链表，因此逆序打印和打印原链表方式一样，因此可以采用递归解决。
  > */
> class Solution {
> public:
>     vector<int> printListFromTailToHead(ListNode* head) {
>         vector<int> v;
>         _printListFromTailToHead(head, v);
>         return v;
>
}
>
> private:
>     void _printListFromTailToHead(ListNode* head, vector<int>& v)
>     {
>         if (head)
>         {
>             _printListFromTailToHead(head->next, v);
>             v.push_back(head->val);
>         }
>     }
>
};
>
> /*
  > 说明：
  >   时间复杂度：O(N)，空间复杂度：O(N)
  >   采用递归打印，代码实现非常简洁，但缺陷是如果链表比较长，有可能会造成递归嵌套太深而造成栈溢出。
  > */
> ```
>
>
>
> ```cpp
> //方法三： 用栈来模拟方法一
> #include <stack>
> class Solution {
> public:
>     vector<int> printListFromTailToHead(ListNode* head) {
>         // 参数检测，如果是空链表，无法打印，直接返回
>         vector<int> ret;
>         if (NULL == head)
>             return ret;
>
>         // 将结点地址保存到栈中(注意：此处最好保存地址，保存结点中数据虽然也可以，但是如果结点中数据时自定义类型，有可能非常大，效率低)
>         stack<ListNode*> s;
>         ListNode* pCur = head;
>         while (pCur)
>         {
>             s.push(pCur);
>             pCur = pCur->next;
>         }
>
>         // 将栈中元素一个一个放到vector中
>         // 注意：此处最好不要使用vector中的push_back方法一个一个插入，因为push_back在插入时有可能
>         //       会扩容，而vector扩容代价非常高(开辟新空间，拷贝元素，释放旧空间)
>         ret.resize(s.size());
>         int index = 0;
>         while (!s.empty())
>         {
>             ret[index++] = s.top()->val;
>             s.pop();
>         }
>
>         return ret;
>
}
>
}
>
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


### 答案-Java-A

传统方式先取出链表的值，然后在对值进行反转

import java.util.ArrayList;

public class Solution {

	public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}

	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		final ArrayList<Integer> values = new ArrayList<Integer>();
		ListNode cur = listNode;
		while (cur != null) {
			values.add(cur.val);
			cur = cur.next;
		}
		final ArrayList<Integer> result = new ArrayList<>(values.size());
		for (int i = values.size() - 1; i >= 0; i--) {
			result.add(values.get(i));
		}
		return result;
	}

}

### 答案-Java-B

通过递归的方式倒序打印链表。

import java.util.ArrayList;

public class Solution {
	public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}
	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		final ArrayList<Integer> values = new ArrayList<Integer>();
		print(listNode, values);
		return values;
	}

	private void print(ListNode listNode, ArrayList<Integer> values) {
		if (listNode != null) {
			print(listNode.next, values);
			values.add(listNode.val);
		}
	}
}

##第3题---已经出过
- 难度：	Easy
- 备注：需要数据结构链表基础，出自《剑指offer》
- 题目描述
输入一个链表，反转链表后，返回链表的所有元素。
###答案C++

> ```ListNode* ReverseList(ListNode* pHead)```
>
> ```cpp
> /*
  > by 时亮益
  > 注意：
  >    1. 该题目在做时，最好不要创建新节点，所以不能直接调用链表中PushBack()方法
  >    2. 给面试官讲解时，要画图结合，更清楚
  >    3. 给面试官讲解时，可以向其说明自己有多种方法，将其他方法简单提下，主要说明自己所写方法，然后说明下自己为什么选择这种方法，可从时间、空间复杂度以及实现算法难以程度进行
  >    4. 如果对链表带环问题比较清楚时，可以向面试官说明：此种方式不能解决带环问题，顺便引导面试官询问自己带环链表问题，正中下怀
  > */
> class Solution {
> public:
>     ListNode* ReverseList(ListNode* pHead) {
>         // 方法一：使用头插法
>         // 不创建新节点，将链表中的结点一个个头插到新链表中即可
>         // 参数检测
>         if (NULL == pHead)
>             return NULL;
>
>         ListNode* pNewHead = NULL;
>         ListNode* pCur = pHead;
>         ListNode* pCurNext = pHead;
>
>         // 将原链表中结点一个一个头插到新链表pNewHead中
>         while (pCur)
>         {
>             pCurNext = pCur->next;
>             pCur->next = pNewHead;
>             pNewHead = pCur;
>             pCur = pCurNext;
>         }
>
>         return pNewHead;
>
}
>
};
>
> class Solution {
> public:
>     ListNode* ReverseList(ListNode* pHead) {
>         // 方法二：使用三个指针
>         ListNode* pPreCur = NULL;
>         ListNode* pCur = pHead;
>         ListNode* pCurNext = NULL;
>
>         /*
		  >         假设已经逆转到以下步骤：
		  >           NULL<-------1        2--------->3-------->4-------->5-------->6-------->7-------->NULL
		  >                   pPreCur     pCur     pCurNext
		  >         逆转步骤：
		  >             1. 先让当前节点pCur指向其前一个节点pPreCur
		  >             2. 三个指针依次向后移动，注意：向后移动时必须先移动pPreCur、pCur、pCurNext
		  >         */
>         while (pCur)
>         {
>             pCurNext = pCur->next;
>             pCur->next = pPreCur;
>             pPreCur = pCur;
>             pCur = pCurNext;
>         }
>
>         return pPreCur;
>
}
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java

public class Solution {

	public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}

	public ListNode ReverseList(ListNode head) {
		ListNode preCur = null;
		ListNode cur = head;
		ListNode nextCur;
		while (cur != null) {
			nextCur = cur.next;
			cur.next = preCur;
			preCur = cur;
			cur = nextCur;
		}
		return preCur;
	}
}

##第4题---已经出过
- 难度：	Easy
- 备注：需要数据结构链表基础，出自《剑指offer》
- 题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
###答案C++

> ```ListNode* Merge(ListNode* pHead1, ListNode* pHead2)```
>
> ```cpp
> // by 时亮益
> class Solution {
> public:
>     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
>     {
>         // 参数检测
>         // 如果两个链表有一个为空，则返回另一个链表
>         if (NULL == pHead1)
>             return pHead2;
>
>         if (NULL == pHead2)
>             return pHead1;
>
>         /*
		  >         上述代码也可按照以下方式写，但是代码的可读性太低
		  >         if(NULL == pHead1 || NULL == pHead2)
		  >             return (NULL == pHead1)? pHead2 : pHead1;
		  >         */
>
>
>         /*
		  >         思路：
		  >         给一个新链表，将两个链表中较小的结点一次向新链表中尾插
		  >         pHead1                                 pHead2
		  >         2------>4------>5----->7----->NULL     3------>5------>6----->8----->NULL
		  >                 p1                             p2
		  >         比如：
		  >         让新链表票pNewHead先指向较小的链表，比如链表1
		  >         给两个指针p1和p2，让p1从pHead1的第二个结点开始，p2指向pHead2的第一个节点
		  >         然后重复以下步骤：
		  >            1. 如果p1和p2结点均存在
		  >            2. 比较p1和p2所指向结点中值的大小
		  >                 如果p1中结点小于等于p2中结点的值，将p1节点尾插到新链表中，p1取其下一个节点
		  >                 否则，将p2结点尾插到新链表中，p2取其下一个结点
		  >            3. 继续步骤1，知道p1或者p2走到链表的末尾
		  >         上述步骤结束后，肯定有一个链表先走到末尾，另一个链表中结点还没有插入完，将另一个链表剩余结点直接尾插到新链表
		  >         */
>
>         ListNode* pL1 = pHead1;
>         ListNode* pL2 = pHead2;
>         ListNode* pNewHead = pHead1;
>         ListNode* pTailNode = pHead1;
>
>         if (pL1->val <= pL2->val)
>         {
>             pL1 = pHead1->next;
>         }
>         else
>         {
>             pNewHead = pTailNode = pHead2;
>             pL2 = pHead2->next;
>         }
>
>         // 将较小的结点向新链表中尾插
>         while (pL1 && pL2)
>         {
>             if (pL1->val <= pL2->val)
>             {
>                 pTailNode->next = pL1;
>                 pL1 = pL1->next;
>             }
>             else
>             {
>                 pTailNode->next = pL2;
>                 pL2 = pL2->next;
>             }
>
>             pTailNode = pTailNode->next;
>         }
>
>         // 循环结束，肯定有一个链表还有节点，将其直接尾插到新链表的末尾
>         if (pL1)
>             pTailNode->next = pL1;
>         else
>             pTailNode->next = pL2;
>
>         return pNewHead;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java

public class Solution {

	public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}

	public ListNode Merge(ListNode list1, ListNode list2) {
		if (list1 == null) {
			return list2;
		}
		if (list2 == null) {
			return list1;
		}
		ListNode pListA = list1;
		ListNode pListB = list2;
		ListNode mHead;
		ListNode mTrail;

		if (pListA.val <= pListB.val) {
			pListA = pListA.next;
			mHead = list1;
			mTrail = list1;
		}
		else {
			pListB = pListB.next;
			mHead = list2;
			mTrail = list2;
		}

		while (pListA != null && pListB != null) {

			if (pListA.val <= pListB.val) {
				mTrail.next = pListA;
				pListA = pListA.next;
			}
			else {
				mTrail.next = pListB;
				pListB = pListB.next;
			}
			mTrail = mTrail.next;
		}

		if (pListA != null) {
			mTrail.next = pListA;
		}
		else {
			mTrail.next = pListB;
		}
		return mHead;
	}
}


##第5题---已经出过
- 难度：	Medium
- 备注：需要数据结构链表基础，出自《剑指offer》
- 题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。
###答案C++

> ```RandomListNode* Clone(RandomListNode* pHead)```
>
> ```cpp
> // by 时亮益
> #include <assert.h>
> class Solution {
> public:
>     RandomListNode* Clone(RandomListNode* pHead)
>     {
>         // 参数检测：如果复杂链表不存在，无法赋值，直接返回
>         if (NULL == pHead)
>             return NULL;
>
>         /*
		  >         1(3)----->2(1)----->3(3)----->4(NULL)----->NULL
		  >         1结点的随即域指向3
		  >         2结点的随即域指向1
		  >         3结点的随即域指向自己
		  >         4结点的随即域指向NULL
		  >         1(3)----->1`----->2(1)----->2`----->3(3)----->3`----->4(NULL)----->4`----->NULL
		  >         */
>         // 在原链表每个结点后插入新节点
>         RandomListNode* pCur = pHead;
>         RandomListNode* pNewNode = NULL;
>         while (pCur)
>         {
>             pNewNode = new RandomListNode(pCur->label);
>             assert(pNewNode);
>             pNewNode->next = pCur->next;
>             pCur->next = pNewNode;
>             pCur = pNewNode->next;
>         }
>
>         /*
		  >         1(3)----->2(1)----->3(3)----->4(NULL)----->NULL
		  >         1(3)----->1`(3`)----->2(1)----->2`(1`)----->3(3)----->3`(3`)----->4(NULL)----->4`(NULL)----->NULL
		  >         */
>         // 给新节点的随机指针域赋值：新节点的随机指针域为旧结点随即域的next
>         pCur = pHead;
>         while (pCur)
>         {
>             pNewNode = pCur->next;
>             if (NULL == pCur->random)
>                 pNewNode->random = NULL;
>             else
>                 pNewNode->random = pCur->random->next;
>
>             pCur = pNewNode->next;
>         }
>
>         /*
		  >         将新节点从原链表中拆下来
		  >         1(3)----->1`(3`)----->2(1)----->2`(1`)----->3(3)----->3`(3`)----->4(NULL)----->4`(NULL)----->NULL
		  >
		  >         原链表：1(3)----->2(1)----->3(3)----->4(NULL)----->NULL
		  >         新链表：1`(3`)----->2`(1`)----->3`(3`)----->4`(NULL)----->NULL;
		  >         */
>         RandomListNode* pNewHead = pHead->next;
>         pCur = pHead;
>         while (pCur->next)
>         {
>             pNewNode = pCur->next;
>             pCur->next = pNewNode->next;
>             pCur = pNewNode;
>         }
>
>         return pNewHead;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第6题---已经出过
- 难度：	Medium
- 备注：需要数据结构链表基础，出自《剑指offer》
- 题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
###答案C++

> ```TreeNode* Convert(TreeNode* pRootOfTree)```
>
> ```cpp
> // by 时亮益
> class Solution {
> public:
>     TreeNode* Convert(TreeNode* pRootOfTree)
>     {
>         // 参数检测
>         if (NULL == pRootOfTree)
>             return NULL;
>
>         // 查找链表的头，即二叉搜索树中最左边结点
>         TreeNode* pHead = pRootOfTree;
>         while (pHead->left)
>         {
>             pHead = pHead->left;
>         }
>
>         // 使用中序线索化的思想进行装换
>         TreeNode* pPrev = NULL;
>         _BSTreeToDList(pRootOfTree, pPrev);
>
>         return pHead;
>     }
>
>     void _BSTreeToDList(TreeNode* pRoot, TreeNode*& pPrev)
>     {
>         if (NULL == pRoot)
>             return;
>
>         // 将当前节点的左子树转化为排序的双向链表
>         _BSTreeToDList(pRoot->left, pPrev);
>
>         // 调整当前节点左指针域的指向，让其指向中序遍历结果中的前驱结点
>         pRoot->left = pPrev;
>         if (pPrev)
>             pPrev->right = pRoot;
>
>         // 用pPrev来标记最近修改过的结点，因为需要将pPrev的改变结果带出去，因此pPrev的类型给成一级指针的引用类型，此处给二级指针也可以
>         pPrev = pRoot;
>
>         // 调整当前节点右指针域的指向，让其指向中序遍历结果中的前驱结点
>         _BSTreeToDList(pRoot->right, pPrev);
>     }
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)‘

##第7题---已经出过
- 难度：	Easy
- 备注：需要数据结构链表基础，出自《剑指offer》
- 题目描述
输入两个链表，找出它们的第一个公共结点。（ps : 链表相交）
###答案C++

> ```ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)```
>
> ```cpp
> // by 时亮益
> class Solution {
> public:
>     ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
>         // 参数检测，如果有一个链表尾空，都不可能有交点
>         if (NULL == pHead1 || NULL == pHead2)
>             return NULL;
>
>         /*
		  >         // 此题为链表相交问题，链表相交时有两种情况：
		  >           1. Y形状
		  >          1----->2-----\
		  >                        \
		  >                         > 3----->4----->5
		  >                        /
		  >          3----->7-----/
		  >
		  >          2. V形状
		  >          1----->2-----4--\
		  >                           \
		  >                            > 3----->4----->5
		  >                           /
		  >          3----->7--------/
		  >
		  >          通关观察发现，让长的链表先走两个链表插入步，然后两个链表同时向后走，相等的结点即为第一个结点
		  >         */
>         int gap = Size(pHead1) - Size(pHead2);
>         ListNode* pL1 = pHead1;
>         ListNode* pL2 = pHead2;
>
>         // 让长的链表先向后走连个链表差值步
>         if (gap > 0)
>         {
>             while (gap--)
>             {
>                 pL1 = pL1->next;
>             }
>         }
>         else
>         {
>             while (gap++)
>             {
>                 pL2 = pL2->next;
>             }
>         }
>
>         // 两个链表同时向后走
>         while (pL1 && pL2)
>         {
>             if (pL1 == pL2)
>                 return pL1;
>
>             pL1 = pL1->next;
>             pL2 = pL2->next;
>         }
>
>         // 两个链表不相交
>         return NULL;
>
}
>
>     // 辅助方法：获取链表中结点的个数
>     size_t Size(ListNode* pHead)
>     {
>         ListNode* pCur = pHead;
>         size_t count = 0;
>         while (pCur)
>         {
>             ++count;
>             pCur = pCur->next;
>         }
>
>         return count;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

### 答案-Java


public class Solution {

	public class ListNode {
		int val;
		ListNode next = null;

		ListNode(int val) {
			this.val = val;
		}
	}

	private int ListNodeLength(ListNode listNode) {
		int len = 0;
		ListNode cur = listNode;
		while (cur != null) {
			len++;
			cur = cur.next;
		}
		return len;
	}

	public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		if (pHead1 == null || pHead2 == null) {
			return null;
		}
		int sub = ListNodeLength(pHead1) - ListNodeLength(pHead2);
		ListNode curA = pHead1;
		ListNode curB = pHead2;
		if (sub > 0) {
			while ((sub--) > 0) {
				curA = curA.next;
			}
		}
		else {
			while (sub++ < 0) {
				curB = curB.next;
			}
		}
		while (curA != null && curB != null) {
			if (curA.val == curB.val) {
				return curA;
			}
			curA = curA.next;
			curB = curB.next;
		}
		return null;
	}
}

##第8.1题---找不到
- 难度：	Medium
- 备注：需要数据结构链表基础，出自《leetcode》
- 题目描述
Given a linked list, determine if it has a cycle in it.
Follow up :
Can you solve it without using extra space ?
			>
> ```bool hasCycle(ListNode *head)```
>
>[来源：牛客 - leetcode](https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=46&tqId=29039&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

##第8.2题---已经出过
- 难度：	Medium

- 备注：需要数据结构链表基础，出自《剑指offer》

- 题目描述

一个链表中包含环，请找出该链表的环的入口结点。（ps：带环问题）
###答案C++

> ```ListNode* EntryNodeOfLoop(ListNode* pHead)```
>
> ```cpp
> // by 时亮益
> class Solution {
> public:
>     ListNode* EntryNodeOfLoop(ListNode* pHead)
>     {
>         // 参数检测：如果链表为空，直接返回
>         if (NULL == pHead)
>             return NULL;
>
>         // 检测链表是否带环
>         // 给两个指针，一个走一步，一个走两步，如果两个指针相遇，则链表带环
>         ListNode* pFast = pHead;
>         ListNode* pSlow = pHead;
>         while (pFast && pFast->next)
>         {
>             pSlow = pSlow->next;
>             pFast = pFast->next->next;
>             if (pSlow == pFast)
>                 break;
>         }
>
>         // 如果链表带环，则一定在环内相遇，pFast或者pFast的next一定不为空
>         if (NULL == pFast || NULL == pFast->next)
>             return NULL;
>
>         /*
		  >         // 链表带环，找入口点
		  >                pH  1
		  >                    |
		  >                    |
		  >                PE  2
		  >                  /   \
		  >                 /     \
		  >                3       7
		  >                |       |
		  >                |       |
		  >                4       6
		  >                 \     /
		  >                  \   /
		  >                    5
		  >                    PM
		  >
		  >
		  >         假设判环是快慢指针在5结点出相遇，设相遇点为PM，环入口点为pE，链表头结点为pH
		  >         假设环的长度为R，从pH到pE的长度为L，从PE到pM的距离为X，则从pM到PE的距离为R - X
		  >         在判环时：
		  >         满指针所在路径：L + X(注意：慢指针进环后，快指针肯定在一圈之内追上慢指针)
		  >         快指针所走路径：L + X + nR(注意：在慢指针进入环后，快指针可能已经在环内转了n圈)
		  >         因为快指针速度为慢指针的2倍，因此
		  >         2 * （L + X） = L + X + nR
		  >         化简：L = nR - X
		  >         取极值：假设n=1，此时L = R - X
		  >         结论：环的入口点--->给两个指针，一个从链表头部开始，一个从相遇点位置开始，两个指针顺着链表的方向同时走，
		  >         当两个指针相遇时，相遇点即为入口点
		  >         */
>         ListNode* pCur = pHead;
>         ListNode* pM = pFast; // pFast即为判环时的相遇点
>         while (pCur != pM)
>         {
>             pCur = pCur->next;
>             pM = pM->next;
>         }
>
>         return pCur;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)

##第9题---已经出过
- 难度：	Easy
- 备注：需要数据结构链表基础，出自《剑指offer》
- 题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
###答案C++

> ```ListNode* deleteDuplication(ListNode* pHead)```
>
> ```cpp
> /*
  > by：时亮益
  > 题目：删除链表中重复的结点(注意：不是去重)
  > 分析：
  > 假设给出以下链表：
  >  1----->1----->1----->2----->3----->3----->4----->4----->5----->NULL
  >  题目要求将所有重复的结点删除掉，因此需要确定重复结点的区间，找到后将该区间中的所有元素删除掉，直到链表中所有重复的结点全部删除完
  >
  >  思路：
  >    pCurPre、pCur、pLast
  >    pCurPre标记已经检测过的不重复的最后一个元素
  >    pCur标记检测到当前节点
  >    pLast标记从pCur开始，到重复元素的下一个位置
  >    即[pCur, pLast)范围中的结点是重复的需要删除
  >
  >    pCur从链表的起始位置开始：
  >    1. 如果pCur不为空
  >    2. 确认重复元素结点的范围【pCur， pLast）
  >    3. 删除【pCur， pLast）区间中的结点
  >    4. 重复1
  > */
>
> class Solution {
> public:
>     ListNode* deleteDuplication(ListNode* pHead)
>     {
>         /*
		  >         // 此处本来需要参数检测，但是在查找重复节点时while本来就是判断，所以次数代码可以省略
		  >         // 参数检测:如果是空链表或者链表中只有一个节点，肯定没有重复节点
		  >         if(NULL == pHead || NULL == pHead->next)
		  >             return pHead;
		  >         */
>
>         ListNode* pCurPre = NULL;
>         // pCur和pLast来标记重复元素的区间
>         ListNode* pCur = pHead;
>         ListNode* pLast = NULL;
>         while (pCur)
>         {
>             // 找重复元素的区间
>             pLast = pCur;
>             while (pLast && pLast->next  && pLast->val == pLast->next->val)
>                 pLast = pLast->next;
>
>             // 当前元素和其下一个位置元素不同
>             if (pCur == pLast)
>             {
>                 pCurPre = pCur;
>                 pCur = pCur->next;
>             }
>             else
>             {
>                 // 用[pCur, pLast)标记重复元素的区间
>                 if (pLast)
>                     pLast = pLast->next;
>
>                 // 删除[pCur, pLast)区间中的所有节点
>                 while (pCur != pLast)
>                 {
>                     ListNode* pDelNode = pCur;
>                     if (pCur == pHead)
>                         pHead = pCur->next;
>                     else
>                         pCurPre->next = pCur->next;
>
>                     pCur = pCur->next;
>                     delete pDelNode;
>                 }
>             }
>         }
>
>         return pHead;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - 剑指offer](https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)


##第10题---已经出过
- 难度：Medium
- 备注：需要数据结构链表基础，出自《Leetcode》
- 题目描述
Given a singly linked list L : L 0→L 1→…→L n - 1→L n,
reorder it to : L 0→L n →L 1→L n - 1→L 2→L n - 2→…
You must do this in - place without altering the nodes' values.
For example,
Given{ 1, 2, 3, 4 }, reorder it to{ 1, 4, 2, 3 }.
###答案C++

> ```void reorderList(ListNode *head)```
>
> ```cpp
> /*
  > by 时亮益
  > 分析：
  >   链表：L0--->L1--->L2--->L3--->L4--->L5--->L6--->NULL
  >         L0--->L6--->L1--->L5--->L2--->L4--->L3--->NULL
  >   从结果来看，此题相当于是将链表后半部分逆序，然后插入到前半部分的每一个结点后
  > */
>
> // 方法一
> #include <vector>
> class Solution {
> public:
>     void reorderList(ListNode *head) {
>         // 参数检测：如果是空链表，直接返回
>         if (NULL == head)
>             return;
>
>         // 将链表每个结点的地址保存到vector中
>         std::vector<ListNode*> v;
>         ListNode* pCur = head;
>         while (pCur)
>         {
>             v.push_back(pCur);
>             pCur = pCur->next;
>         }
>
>         // left从左边开始，right从右侧开始，
>         // 先改变left标记位置结点的指向，让其next指向right标记结点，left超后走
>         // 再改变right标记位置结点的指针，让其next指向left标记结点，right超前走
>         // 直到left与right相遇，更新完毕
>         // 出了循环，中间位置结点刚好成新链表的最后一个节点，将其next位置NULL
>         int left = 0, right = v.size() - 1;
>         while (left < right)
>         {
>             v[left++]->next = v[right];
>             v[right--]->next = v[left];
>         }
>
>         v[left]->next = NULL;
>
}
>
};
>
> /*
  > 说明：
  >   此方法非常简单，但是其时间复杂度为O(N), 空间复杂度为：O(N)
  > */
>
> // 方法二：
> class Solution {
> public:
>     void reorderList(ListNode *head) {
>         // 参数检测：如果是空链表或者链表中只有一个节点，直接返回
>         if (NULL == head || NULL == head->next)
>             return;
>
>         // 找到链表的中间结点
>         ListNode* pFast = head;
>         ListNode* pSlow = head;
>         while (pFast && pFast->next)
>         {
>             pFast = pFast->next->next;
>             pSlow = pSlow->next;
>         }
>
>         // 从中间结点开始，将链表分成两个链表
>         ListNode* pCur1 = head;
>         ListNode* pCur2 = pSlow->next;
>         pSlow->next = NULL;
>
>         // 对链表的后半部分进行逆置
>         pCur2 = _ReverseList(pCur2);
>
>         // 将第二个链表中每个结点一次插入到第一个链表每一个结点后
>         ListNode* pTailNode = pCur1;
>         pCur1 = pCur1->next;
>
>         while (pCur1 && pCur2)
>         {
>             // 将第二个链表中结点尾插到新链表中
>             pTailNode->next = pCur2;
>             pTailNode = pCur2;
>             pCur2 = pCur2->next;
>
>             // 将第一个链表中结点尾插到新链表中
>             pTailNode->next = pCur1;
>             pTailNode = pCur1;
>             pCur1 = pCur1->next;
>         }
>
>         // 将剩余结点连接到新链表的末尾
>         if (pCur1)
>             pTailNode->next = pCur1;
>         else
>             pTailNode->next = pCur2;
>
}
>
> private:
>     // 单链表逆置
>     ListNode* _ReverseList(ListNode* pHead)
>     {
>         ListNode* pNewHead = NULL;
>         ListNode* pCur = pHead;
>         ListNode* pCurNext = NULL;
>
>         while (pCur)
>         {
>             pCurNext = pCur->next;
>             pCur->next = pNewHead;
>             pNewHead = pCur;
>             pCur = pCurNext;
>         }
>
>         return pNewHead;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=46&tqId=29037&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

##第11题---已经出过
- 难度：Hard
- 备注：需要数据结构链表基础，出自《Leetcode》
- 题目描述
Sort a linked list in O(n log n) time using constant space complexity.
###答案C++

> ```ListNode *sortList(ListNode *head)```
>
> ```cpp
> // by 时亮益
> // 使用快速排序原理对链表进行排序
> class Solution {
> public:
>     ListNode *sortList(ListNode *head) {
>         _sortList(head, NULL);
>         return head;
>
}
>
> private:
>     ListNode *_sortList(ListNode* pHead, ListNode* pTail)
>     {
>         // 链表尾空，或者链表中只剩余一个节点，不用排序
>         if (pTail == pHead || pHead->next == pTail)
>             return pHead;
>
>         // 通过_Pation()方法，将链表按照基准值分割成前后两部分
>         ListNode* pMiddle = _Pation(pHead, pTail);
>
>         // 递归排链表的左半部分
>         _sortList(pHead, pMiddle);
>
>         // 递归排链表的右半部分
>         _sortList(pMiddle->next, pTail);
>
>         return pHead;
>     }
>
>     /*
	  >     取链pHead中元素作为基准值，将序列分割成比基准值小的做部分和比基准值大的右半部分
	  >     采用前后指针版本的快排分割数据原理
	  >     */
>     ListNode* _Pation(ListNode* pHead, ListNode* pTail)
>     {
>         ListNode* pPreCur = pHead;
>         ListNode* pCur = pHead->next;
>         int key = pHead->val;
>
>         while (pCur != pTail)
>         {
>             if (pCur->val < key)
>{
>                 pPreCur = pPreCur->next;
>                 if (pPreCur != pCur)
>                     swap(pCur->val, pPreCur->val);
> }
>
>             pCur = pCur->next;
>         }
>
>         if (pPreCur != pHead)
>             swap(pPreCur->val, pHead->val);
>
>         // 返回基准值所在结点
>         return pPreCur;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/d75c232a0405427098a8d1627930bea6?tpId=46&tqId=29033&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

##第12题---已经出过
- 难度：Hard
- 备注：需要数据结构链表基础、二叉树，出自《Leetcode》
- 题目描述
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
###答案C++

> ```TreeNode *sortedListToBST(ListNode *head)```
>
> ```cpp
> // by 时亮益
> class Solution {
> public:
>     TreeNode *sortedListToBST(ListNode *head) {
>         // 参数检测：如果链表尾空链表，则二叉树为空
>         if (NULL == head)
>             return NULL;
>
>         return _sortedListToBST(head, NULL);
>
}
>
> private:
>     // 根据二叉树前序遍历规则创建BST
>     TreeNode* _sortedListToBST(ListNode *pHead, ListNode* pTail)
>     {
>         if (pHead == pTail)
>             return NULL;
>
>         // 因为链表已经排序，题目要求创建的二叉树为平衡二叉树
>         // 因此将链表的中间结点作为二叉树的根节点
>         ListNode* pMiddle = _FindMiddleNode(pHead, pTail);
>         TreeNode* pRoot = new TreeNode(pMiddle->val);
>
>         // 用链表中间结点的左半边去递归创建pRoot的左子树
>         pRoot->left = _sortedListToBST(pHead, pMiddle);
>
>         // 用链表中间结点的左半边去递归创建pRoot的右子树
>         pRoot->right = _sortedListToBST(pMiddle->next, pTail);
>
>         return pRoot;
>     }
>
>     // 查找链表的中间结点
>     ListNode* _FindMiddleNode(ListNode* pHead, ListNode* pTail)
>     {
>         ListNode* pFast = pHead;
>         ListNode* pSlow = pHead;
>
>         while (pFast != pTail && pFast->next != pTail)
>         {
>             pFast = pFast->next->next;
>             pSlow = pSlow->next;
>         }
>
>         return pSlow;
>     }
>
};
> ```
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/86343165c18a4069ab0ab30c32b1afd0?tpId=46&tqId=29069&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

##第13题---已经出过
- 难度：Hard
- 备注：需要数据结构链表基础，出自《Leetcode》
- 题目描述
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given1->4->3->2->5->2and x = 3,
return1->2->2->4->3->5.
###答案C++

> ```ListNode *partition(ListNode *head, int x)```
>
> ```cpp
> /*
  > by：时亮益
  > 题目：按照指定值x将链表分割成两部分，前面全部比x小，后面结点大于等于x
  > 链表： 1->4->3->2->5->2->NULL
  > 输入x：3
  > 输出： 1->2->2->4->3->5->NULL
  > 从输出结果可以看出：小的结点保持在原链表中小于的次序
  >                   大于等于的结点保持在原链表中的大于等于次序
  >
  > 初次看到此题，感觉与快速排序分割算法类似，但是快排的分割不稳定，而本题需要稳定的算法。
  >
  > 思路：
  >   创建两个新链表minList和maxList
  >   将小于x的结点尾插到minList中，将大于等于x的结点尾插到maxList中
  >   将maxList链表链接在minList末尾
  > */
> class Solution {
> public:
>     ListNode *partition(ListNode *head, int x) {
>         // 参数检测：空链表或者链表中只有一个节点，直接返回
>         if (NULL == head)
>             return head;
>
>         ListNode* minList = NULL;
>         ListNode* minListTail = NULL;
>         ListNode* maxList = NULL;
>         ListNode* maxListTail = NULL;
>         ListNode* pCur = head;
>
>         // 将原链表中结点分离开
>         // 小于x的结点尾插到minList中 大于等于x的结点尾插到maxList中
>         while (pCur)
>         {
>             if (pCur->val < x)
>{
>                 if (minList)
>                     minListTail->next = pCur;
>                 else
>                     minList = pCur;
>
>                  minListTail = pCur;
> }
>             else
>             {
>                 if (maxList)
>                     maxListTail->next = pCur;
>                 else
>                     maxList = pCur;
>                 maxListTail = pCur;
>             }
>
>             pCur = pCur->next;
>         }
>
>         // 将两个链表最后一个节点的next指针域置空
>         if (maxListTail)
>             maxListTail->next = NULL;
>
>         if (minListTail)
>             minListTail->next = NULL;
>
>         // 将maxList链表链接在minList末尾
>         if (minListTail)
>         {
>             minListTail->next = maxList;
>             return minList;
>         }
>
>         return maxList;
>
}
>
};
> ```
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/1dc1036be38f45f19000e48abe00b12f?tpId=46&tqId=29092&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

##第14题---已经出过
- 难度：Hard
- 备注：需要数据结构链表基础，出自《Leetcode》
- 题目描述
Given a list, rotate the list to the right by k places, where k is non - negative.
For example :
Given1->2->3->4->5->NULLand k = 2,
return4->5->1->2->3->NULL.
###答案C++

> ```ListNode *rotateRight(ListNode *head, int k)```
>
> ```cpp
> /*
  > by 时亮益
  > 题目：链表的循环移位
  >      链表： 1->2->3->4->5->NULL  当K为2时，将链表后两个结点移动到链表的起始位置
  >      移动后链表： 4->5->1->2->3->NULL
  >
  > 思路：
  >   1. 先将链表构成一个环，并记录链表中结点的个数count
  >   2. 确定k的值(因为k可能大于链表中结点的个数，如果大于，用k对链表中结点的个数取模 k = k%count)
  >   3. 移动结点
  >      即在链表中找到移动之后新链表的头，右移k个结点，反过来想就是让一个指针从链表的头部往后走count-k
  >      步，pCur位置即为移动之后新链表的头。
  >   4. 将环断开
  >
  > */
> #include <assert.h>
> class Solution {
> public:
>     ListNode *rotateRight(ListNode *head, int k) {
>         // 参数检测
>         if (NULL == head)
>             return NULL;
>         // 题目说明：k为非负数，此处对k断言下
>         assert(k >= 0);
>
>         // 获取链表中结点的个数，顺表记录链表的尾结点
>         int count = 0;
>         ListNode* pCur = head;
>         ListNode* pPreCur = NULL;
>         while (pCur)
>         {
>             count++;
>             pPreCur = pCur;
>             pCur = pCur->next;
>         }
>
>         // 将链表构成环
>         pPreCur->next = head;
>
>         // 如果k大于等于链表中结点的个数，将其对链表长度取模
>         k %= count;
>         k = count - k;
>
>         pCur = head;
>         while (k--)
>         {
>             pPreCur = pCur;
>             pCur = pCur->next;
>         }
>
>         pPreCur->next = NULL;
>         return pCur;
>
}
>
};
> ```
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/afbec6b9d4564c63b2c149ccc01c5678?tpId=46&tqId=29118&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

##第15题---已经出过
- 难度：Easy

- 备注：需要数据结构链表基础，出自《Leetcode》

- 题目描述
Given a linked list, remove the n th node from the end of list and return its head.
For example,
Given linked list : 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note :
	 Given n will always be valid.
	 Try to do this in one pass
###答案C++

> ```ListNode *removeNthFromEnd(ListNode *head, int n)```
>
> ```cpp
> /*
  > by 时亮益
  > 题目：删除链表的倒数第n个结点
  > 思路：
  >    1. 找到链表的倒数第n个结点
  >    2. 删除倒数第n个结点，删除时需要对倒数第n个结点分情况：
  >         >> 头结点
  >         >> 非头结点
  > */
>
> class Solution {
> public:
>     ListNode *removeNthFromEnd(ListNode *head, int n) {
>         // 参数检测
>         if (NULL == head || n <= 0)
>             return head;
>
>         // 找倒数第K个结点
>         // 让一个指针先走n步
>         ListNode* pFast = head;
>         while (n--)
>         {
>             // n大于链表中结点的个数，无法删除
>             if (NULL == pFast)
>                 return head;
>
>             pFast = pFast->next;
>         }
>
>         // 两个指针同时超后走，直到pFast指针走到链表的末尾
>         ListNode* pSlow = head;
>         ListNode* pPreSlow = NULL;
>         while (pFast)
>         {
>             pFast = pFast->next;
>             pPreSlow = pSlow;
>             pSlow = pSlow->next;
>         }
>
>         // 删除节点：头结点和非头结点
>         if (pSlow == head)
>             head = head->next;
>         else
>             pPreSlow->next = pSlow->next;
>
>         delete pSlow;
>
>         return head;
>
}
>
};
> ```
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=46&tqId=29159&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)


##第16题---已经出过
- 难度：Hard
- 备注：需要数据结构链表基础，出自《Leetcode》
- 题目描述
You are given two linked lists representing two non - negative numbers.The digits are stored in reverse order and each of their nodes contain a single digit.Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
   Output : 7 -> 0 -> 8
###答案C++

> ```ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)```
>
> ```cpp
> /*
  > by：时亮益
  > 题目：将两个链表中相同位置结点中的数据相加，此题实际是大数的加法运算，只不过是将大数的每位数字由低位到高位保存在链表的结点中
  > 情况一：
  > 两个链表的长度相同
  > 1--->2--->3---NULL
  > 2--->3--->4---NULL
  > 返回：
  > 3--->5--->7--->NULL
  >
  > 情况二：
  > 两个链表的长度不同
  > 1--->2--->3--->4--->5--->NULL
  > 1--->0--->NULL
  > 返回：
  > 2--->2--->3--->4--->5--->NULL
  >
  > 情况三：
  > 加完之后最后还有一个进位
  > 9--->9--->9--->NULL
  > 9--->9--->NULL
  > 返回：
  > 8--->9--->0--->1--->NULL
  > 加完之后，最后还有一个进位需要处理
  >
  > 思路：
  >  1. 将两个链表相同位置的数据进行相加，如果有低位的进位还需要加上进位
  >  2. 如果有一个链表中的数据没有加完，将其中的值移动到新链表中，注意加进位
  >  3. 如果最后有进位，还需要再加上进位
  >
  >  注意：因为加法不能改变左右操作数的内容，因此此题将加完之后的结果保存在新链表中
  > */
>
> class Solution {
> public:
>     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
>         // 参数检测，如果两个链表有一个为空，则返回另外一个
>         if (NULL == l1)
>             return l2;
>
>         if (NULL == l2)
>             return l1;
>
>         // step表示进位，data来代表某位加完之后的结果
>         // 先加最低位，如果有进位，需要保存进位
>         int step = 0;
>         int data = l1->val + l2->val;
>         if (data > 9)
>         {
>             step = 1;
>             data -= 10;
>         }
>
>         ListNode* pNewHead = new ListNode(data);
>         ListNode* pTailNode = pNewHead;
>
>         ListNode* pCur1 = l1->next;
>         ListNode* pCur2 = l2->next;
>         // 将两个链表对应结点中的数据相加，注意进位
>         while (pCur1 && pCur2)
>         {
>             data = pCur1->val + pCur2->val + step;
>             step = 0;
>             if (data > 9)
>             {
>                 data -= 10;
>                 step = 1;
>             }
>
>             // 将加完之后的结果尾插到新链表中
>             pTailNode->next = new ListNode(data);
>             pTailNode = pTailNode->next;
>             pCur1 = pCur1->next;
>             pCur2 = pCur2->next;
>         }
>
>         /*
		  >           记录较长的链表
		  >         1--->2--->3--->4--->5--->NULL
		  >         1--->0--->NULL
		  >         */
>         ListNode* pCur = pCur1;
>         if (NULL == pCur)
>             pCur = pCur2;
>
>         /*
		  >         如果两个链表的长度不同，将较长链表中剩余的结点尾插到新链表中，注意进位
		  >         加完之后最后还有一个进位
		  >          9--->9--->9--->NULL
		  >          9--->9--->NULL
		  >         */
>         while (pCur)
>         {
>             data = pCur->val + step;
>             step = 0;
>             if (data > 9)
>             {
>                 data -= 10;
>                 step = 1;
>             }
>             pTailNode->next = new ListNode(data);
>             pTailNode = pTailNode->next;
>              pCur = pCur->next;
>         }
>
>         if (step)
>             pTailNode->next = new ListNode(1);
>
>         return pNewHead;
>
}
>
};
> ```
>
>
>
>
>
>[来源：牛客 - Leetcode](https://www.nowcoder.com/practice/56f8d422eae04f129c8e5a05299ae275?tpId=46&tqId=29174&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking)

#栈和队列

## 第1题---已经出过

- 难度：Easy

- 备注：需要数据结构栈的基础，出自《剑指offer》

- 题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

https ://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

### 答案C++

```cpp
/*
题目：用两个栈实现一个队列----by 时亮益
分析：
栈特性：后进先出
队列特性：先进先出

用两个栈来模拟实现一个队列时，即用栈的特性模拟出队列的特性
假如入队列的数据为：1 2 3 4 5
入队列操作：
将所有入队列的数据放到stack1中

出队列：
由于栈的特性是后进先出，队列的特性是先进先出，因此不能直接从stack1中出数据，需要将stack1中的数据全部导到stack2中，每次出元素时从stack2中出，直到stack2为空时，再从stack1中导数据到stack2
*/
class Solution
{
public:
	void push(int node) {
		// 令stack1存放入队列的数据，每次入队列时，从将数据保存到stack1中
		stack1.push(node);
	}

	int pop() {
		// 每次出队列时，从stack2中出队列，当stack2中没有数据时，再将stack1中的数据移到stack2中
		if (stack2.empty())
		{
			while (!stack1.empty())
			{
				stack2.push(stack1.top());
				stack1.pop();
			}
		}

		int data = stack2.top();
		stack2.pop();

		return data;
	}

private:
	stack<int> stack1;
	stack<int> stack2;
};
```



## 第2题---已经出过

- 难度：Easy

- 备注：需要数据结构栈的基础，出自《剑指offer》

- 题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数

https ://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

### 答案C++

```cpp
#include <stack>
class Solution {
public:
	void push(int value) {
		int minData = value;
		if (!_s.empty() && _s.top() < minData)
			minData = _s.top();

		_s.push(value);
		_s.push(minData);
	}
	void pop() {
		_s.pop();
		_s.pop();
	}
	int top() {
		int minData = _s.top();
		_s.pop();
		int data = _s.top();
		_s.push(minData);
		return minData;
	}
	int min() {
		return _s.top();
	}

private:
	std::stack<int> _s;
};

/*
*/

#include <stack>
class Solution {
	struct SElem
	{
		SElem(int data, int minData)
		: _data(data)
		, _minData(minData)
		{}

		int _data;
		int _minData;
	};

public:
	void push(int value) {
		SElem elem(value, value);
		if (!_s.empty() && _s.top()._minData < value)
			elem._minData = _s.top()._minData;

		_s.push(elem);
	}
	void pop() {
		_s.pop();
	}
	int top() {
		return _s.top()._data;
	}
	int min() {
		return _s.top()._minData;
	}

private:
	std::stack<SElem> _s;
};


#include <stack>
class Solution {
public:
	void push(int value) {
		_data.push(value);
		if (_minData.empty() || value <= _minData.top())
			_minData.push(value);
	}
	void pop() {
		if (_data.top() == _minData.top())
			_minData.pop();
		_data.pop();
	}
	int top() {
		return _data.top();
	}
	int min() {
		return _minData.top();
	}

private:
	std::stack<int> _minData;
	std::stack<int> _data;
};
```



##第3题---已经出过

- 难度：Easy

- 备注：需要数据结构栈的基础，出自《剑指offer》

- 题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1, 2, 3, 4, 5是某栈的压入顺序，序列4，5, 3, 2, 1是该压栈序列对应的一个弹出序列，但4, 3, 5, 1, 2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

https ://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

### 答案

```cpp
#include <stack>
class Solution {
public:
	bool IsPopOrder(vector<int> pushV, vector<int> popV) {
		// 参数检测，如果两个vector中的数据个数不同，则入栈出栈一定有问题
		if (pushV.size() != popV.size())
			return false;

		stack<int> s;
		int inIdx = 0, outIdx = 0;
		int inSize = pushV.size();
		int outSize = popV.size();

		while (outIdx < outSize)
		{
			while (s.empty() || s.top() != popV[outIdx])
			{
				if (inIdx < inSize)
					s.push(pushV[inIdx++]);
				else
					return false;
			}

			s.pop();
			++outIdx;
		}

		return true;
	}
};
```



##第4题---与第一题重复

- 难度：Easy

- 备注：需要数据结构栈的基础，出自《剑指offer》

- 题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

https ://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=8&&tqId=11008&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

##第5题---已经出过

- 难度：Easy

- 备注：需要数据结构栈以及STL知识，出自《程序员面试金典》

- 题目描述

请实现一种数据结构SetOfStacks，由多个栈组成，其中每个栈的大小为size，当前一个栈填满时，新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。

给定一个操作序列int[][2] * *ope**(C++为vector&ltvector&ltint >> )，每个操作的第一个数代表操作类型，若为1，则为push操作，后一个数为应push的数字；若为2，则为pop操作，后一个数无意义。请返回一个int[][](C++为vector&ltvector&ltint >> )，为完成所有操作后的SetOfStacks，顺序应为从下到上，默认初始的SetOfStacks为空。保证数据合法

## 第6题---已经出过

- 难度：Middle

- 备注：需要数据结构栈和STL vector知识，出自《程序员面试金典》

- 题目描述

请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

给定一个int[] * *numbers**(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素

https ://www.nowcoder.com/practice/d0d0cddc1489476da6b782a6301e7dec?tpId=8&&tqId=11009&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

### 答案C++

```cpp
#include <algorithm>
class TwoStacks {
public:
	vector<int> twoStacksSort(vector<int> numbers) {
		// 调用sort方法对vector中的元素排序
		std::sort(numbers.begin(), numbers.end());

		// 调用reverse方法，将vector中的元素逆序过来
		std::reverse(numbers.begin(), numbers.end());
		return numbers;
	}
};


class TwoStacks {
public:
	vector<int> twoStacksSort(vector<int> numbers) {
		vector<int> ret;
		while (!numbers.empty())
		{
			int temp = numbers.back();  //假设vector的最后一个元素就是栈顶。  
			numbers.pop_back();

			while (!ret.empty() && ret.back() > temp)//当辅助栈中的栈顶元素大于原栈的栈顶元素的时候，将辅助栈的栈顶元素出栈到原栈中。  
			{

				numbers.push_back(ret.back());
				ret.pop_back();
			}
			ret.push_back(temp);

		} //排序完成后，ret是升序。  
		while (!ret.empty()) //将ret中的元素降序。  
		{
			numbers.push_back(ret.back());
			ret.pop_back();
		}
		return numbers;
	}
};
```



##第7题---已经出过

- 难度：Easy

- 备注：需要数据结构队列的基础知识，出自《leetcode》

- 题目描述

Evaluate the value of an arithmetic expression in[Reverse Polish Notation](http://en.wikipedia.org/wiki/Reverse_Polish_notation).

Valid operators are + , -, *, / .Each operand may be an integer or another expression.

Some examples :

https ://www.nowcoder.com/practice/22f9d7dd89374b6c8289e44237c70447?tpId=46&tqId=29031&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第8题---已经出过

	- 难度：Easy

	- 备注：需要数据结构栈的基础知识

	- 题目描述

	堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。Push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

	- 输入描述

	```
	对于每组测试数据，第一行是一个正整数 n，0<n <= 10000(n = 0 结束)。而后的 n 行，每行的第一个字符可能是'P’或者'O’或者'A’；如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O’，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是'A’，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空
	```

	- 输出描述

	```
	对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A’操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E’。当每组测试数据完成后，输出一个空行
	```

	​      https ://www.nowcoder.com/practice/e91982a145944ceab6bb9a4a508e0e26?tpId=40&&tqId=21511&rp=1&ru=/activity/oj&qru=/ta/kaoyan/question-ranking

### 答案C++

	   ```cpp
		   // by 时亮益
#include <stdio.h>
#include <stack>

		   int main()
	   {
			   std::stack<int> s;
			   // 因为可能要验证多次操作，因此外层给一个死循环，for(;;)表示死循环的效率比较高
			   for (;;)
			   {
				   // 读取操作总行数
				   int n = 0;
				   scanf("%d", &n);
				   if (0 == n)
					   return 0;

				   while (n--)
				   {
					   getchar();  // 接收总行数后面的换行字符
					   char op = getchar();
					   switch (op)
					   {
					   case 'P':  // 压栈
					   {
									  int data = 0;
									  getchar();   // 接收操作(P O A)操作后的换行
									  scanf("%d", &data);
									  s.push(data);
									  break;
					   }
					   case 'O':  // 出栈，当栈空时，不进行任何操作
					   {
									  if (!s.empty())
										  s.pop();
									  break;
					   }
					   case 'A':   // 访问元素
					   {
									   // 当栈中元素空，输出'E',否则输出栈顶元素
									   if (s.empty())
										   printf("E\n");
									   else
										   printf("%d\n", s.top());
									   break;
					   }
					   }
				   }

				   printf("\n");   // 本轮操作结束，输出空行
			   }

			   return 0;
		   }
	   ```



## 第9题---已经出过

		   - 难度：Easy

		   - 备注：需要数据结构栈的基础知识

		   - 题目描述

		   一个栈依次压入1, 2, 3, 4, 5那么从栈顶到栈底分别为5, 4, 3, 2, 1。将这个栈转置后，从栈顶到栈底为1, 2, 3, 4, 5，也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，但是只能用递归函数来实现，而不能用另外的数据结构。

		   给定一个栈**Stack**以及栈的大小**top**，请返回逆序后的栈

	   https ://www.nowcoder.com/practice/ba7d7f5d1edf4d1690d66e12e951f6ea?tpId=49&&tqId=29367&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

### 答案C++

	   ```cpp
		   /*
		   by：时亮益
		   题目：对栈中数据进行逆序
		   */
		   /*
		   方法一：最简答的方式是对栈中的数据用reverse方法进行逆序，虽然可以通过编译，通过所有的测试用例，但是
		   不满足题目的要求，题目要求必须使用递归进行实现
		   */
	   class ReverseStack {
	   public:
		   vector<int> reverseStackRecursively(vector<int> stack, int top) {
			   std::reverse(stack.begin(), stack.end());
			   return stack;
		   }
	   };

	   /*
	   */
	   ```



# 二叉树

## 第1题---已经出过

		   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行

	   https ://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=13&&tqId=11213&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking



## 第2题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   操作给定的二叉树，将其变换为源二叉树的镜像

		   二叉树的镜像定义：源二叉树

		   ​    	    8
		   / \
		   6       10
		   / \ / \
		   5     7  9   11

		   镜像二叉树
		   8
		   / \
		   10        6
		   / \ / \

		   11      9 7      5

	   https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking



##第3题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度

	   https ://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=11191&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第4题

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes, 否则输出No。假设输入的数组的任意两个数字都互不相同 。

	   https ://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第5题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   输入一棵二叉树，判断该二叉树是否是平衡二叉树

	   https ://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第6题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针

	   https ://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第7题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{ 1, 2, 4, 7, 3, 5, 6, 8 }和中序遍历序列{ 4, 7, 2, 1, 5, 3, 8, 6 }，则重建二叉树并返回

	   https ://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第8题---已经出过

	   - 难度：Middle

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的

	   https ://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第9题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行

	   https ://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=13&tqId=11213&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第10题

	   - 难度：Hard

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   请实现两个函数，分别用来序列化和反序列化二叉树

	   https ://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第11题

	   - 难度：Hard

		   - 备注：需要数据结构二叉树的基础知识，出自《剑指offer》

		   - 题目描述

		   输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

	   https ://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

## 第12题---已经出过

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

		   - 题目描述

		   Given a binary tree, return the *preorder* traversal of its nodes' values 

		   For example : Given binary tree{ 1, #, 2, 3 },

		   1
		   \
		   2
		   /
		   3

		   return[1, 2, 3].

		   **Note:** Recursive solution is trivial, could you do it iteratively ?

	   https ://www.nowcoder.com/practice/501fb3ca49bb4474bf5fa87274e884b4?tpId=46&tqId=29036&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第13题---已经出过

			  - 难度：Easy

			  - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

			  - 题目描述

			  Given a binary tree, return the postorder traversal of its nodes' values.

			  For example :

	   Given binary tree{ 1, #, 2, 3 },

		   1
		   \
		   2
		   /
		   3

		   return[3, 2, 1].

		   **Note:** Recursive solution is trivial, could you do it iteratively ?

	   https ://www.nowcoder.com/practice/32af374b322342b68460e6fd2641dd1b?tpId=46&tqId=29035&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第14题---已经出过

			  - 难度：Middle

			  - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

			  - 题目描述

			  Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node

		  https ://www.nowcoder.com/practice/e08819cfdeb34985a8de9c4e6562e724?tpId=46&tqId=29030&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第15题

	   - 难度：Hard

		   - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

		   - 题目描述

		   Given a binary tree, find the maximum path sum.

		   The path may start and end at any node in the tree.

		   For example :
	   Given the below binary tree,

		   ​       1
		   / \
		   2      3

		   return6.

	   https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=46&tqId=29056&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第16题---已经出过

	   - 难度：Middle

		   - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

		   - 题目描述

		   Given inorder and postorder traversal of a tree, construct the binary tree.

		   **Note:**
		   You may assume that duplicates do not exist in the tree.

	   https ://www.nowcoder.com/practice/b0d07d0edc7f495696aecd265d5ef1b9?tpId=46&tqId=29072&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第17题

			  - 难度：Middle

			  - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

			  - 题目描述

			  Given two binary trees, write a function to check if they are equal or not.

			  Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

		  https://www.nowcoder.com/practice/9a9e74b71f944efab9992925f7f9a65e?tpId=46&tqId=29078&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第18题

	   - 难度：Middle

		   - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

		   - 题目描述

		   Two elements of a binary search tree(BST) are swapped by mistake.

		   Recover the tree without changing its structure.

		   Note：

		   A solution using O(n) space is pretty straight forward.Could you devise a constant space solution ?

	   https ://www.nowcoder.com/practice/67c7172122b54b748e78eac7b183b5f3?tpId=46&tqId=29079&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第19题

			  - 难度：Middle

			  - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

			  - 题目描述

			  Given a binary tree, determine if it is a valid binary search tree(BST).

			  Assume a BST is defined as follows :

	   -The left subtree of a node contains only nodes with keys **less than** the node's key.
		   - The right subtree of a node contains only nodes with keys **greater than** the node's key.
		   - Both the left and right subtrees must also be binary search trees.

	   https ://www.nowcoder.com/practice/fd7f880072914464a13b89af242c0ce5?tpId=46&tqId=29080&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第20题

			  - 难度：Hard

			  - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

			  - 题目描述

			  Given *n*, generate all structurally unique **BST's** (binary search trees) that store values 1...*n*.

			  For example,
			  Given *n* = 3, your program should return all 5 unique BST's shown below.

			  1            3          3          2      1
			  \ / / / \      \
			  3      2         1         1      3      2
			  / / \                           \
			  2     1              2                           3

		  https://www.nowcoder.com/practice/98aaaefacaca44b9b4f2f2bd75780664?tpId=46&tqId=29082&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

## 第21题

	   - 难度：Easy

		   - 备注：需要数据结构二叉树的基础知识，出自《LeetCode》

		   - 题目描述

		   Given a binary tree, return the *inorder* traversal of its nodes' values.

		   For example :
	   Given binary tree{ 1, #, 2, 3 },

		   1
		   \
		   2
		   /
		   3

		   return[1, 3, 2].

		   **Note:** Recursive solution is trivial, could you do it iteratively ?

	   https ://www.nowcoder.com/practice/1b25a41f25f241228abd7eb9b768ab9b?tpId=46&tqId=29084&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking



